//
// Created by ttao on 2022/7/25.
//
#include "tree.h"

/* ================ start of tree.c ================ */
#define NODEATTR(A) (node->attr & NODE_ATTR_MASK & A)?TRUE:FALSE

#define EXCHAN_GTARGET_NODE(D, S, X, Y) D->spot->X = S->spot->Y; \
                                        if(ISNOTNULL(D->spot->X))         \
                                            D->spot->X->spot->parent = D
//将S的左右子节点赋给D
#define EXCHANG_NODE(D, S) EXCHAN_GTARGET_NODE(D, S, left, left); \
                           EXCHAN_GTARGET_NODE(D, S, right, right)
// 交换父节点
#define EXCHANG_PARENT(D, S) noder __parent_t_ = D->spot->parent;  \
                            D->spot->parent = S->spot->parent; \
                            S->spot->parent = __parent_t_


static inline int hashcmp(const char *s1, const char *s2)
//若s1=s2，则返回零；若s1<s2，则返回负数；若s1>s2，则返回正数
{
    if(ISNULL(s1) || ISNULL(s2)) return 0;
    return strcmp(s1, s2);
}

/*
 * 获取节点关系网
 * g, p, u  -- 祖父 父亲 叔叔
 * dl, dr   -- 待删除节点左孩子 待删除节点右孩子
 * ul, ur   -- 左表 右表
 * b      -- 兄弟节点
 * bl, br -- 左侄子 右侄子
 * */
#define NODE_RELATION_NET(D)     noder g,p,u;                        \
                                _rbtreeppapaunode(D, &g, &p, &u);                       \
                                noder dl = D->spot->left;             \
                                noder dr = D->spot->right;            \
                                noder ul = NULL,ur = NULL;                              \
                                if(ISNOTNULL(u))                                           \
                                {                                                       \
                                    ul = u->spot->left;                           \
                                    ur = u->spot->right;                          \
                                }                                                        \
                                noder b = getBrother(D);                        \
                                noder bl = NULL, br = NULL;                             \
                                if(ISNOTNULL(b))                                        \
                                {                                                       \
                                    bl = b->spot->left;                           \
                                    br = b->spot->right;                          \
                                }
// 新增节点
static inline noder _newnode(void *keyvalue, void *nodevalue, uint8_t attr)
{

    if(ISNULL(keyvalue)) return NULL;
    struct Spot* spot = (struct Spot*)http_malloc(http_malloc_align(sizeof(struct Spot)));
    memset(spot, 0, sizeof(struct Spot));
    noder node = (noder) http_malloc(http_malloc_align(sizeof(struct Node)));
    memset(node, 0, http_malloc_align(sizeof(struct Node)));
    spot->right = NULL;
    spot->left = NULL;
    spot->parent = NULL;
    char *key = http_malloc(sizeof(char) * http_malloc_align(strlen(keyvalue)));
    memset(key, 0, http_malloc_align(strlen(keyvalue)));
    memcpy(key, keyvalue, strlen(keyvalue));
    void* value = nodevalue;;
    if(ISNULL(value)) {
        if(ISNOTNULL(spot)) http_free(spot);
        if(ISNOTNULL(node)) http_free(node);
        return NULL;
    }
    spot->value = value;
    node->key = key;
    node->spot = spot;
    node->attr = attr;
    node->color = RBTREE_COLOR_RED;
    setnodeisleaf(node);   // 新加入的节点默认都是叶子节点
    return node;
}

static inline void _destroynode(noder node) {
    if(ISNULL(node))return;
    if(ISNOTNULL(node->key)) http_free(node->key);
    if(ISNOTNULL(node->spot)) http_free(node->spot);
    http_free(node);
}

noder treenodenew(char *key, void *value)
{
    if(ISNULL(key)) return NULL;
    return _newnode(key, value, 0);
}

void treenodedestroy(noder  node)
/*销毁*/
{
    if(ISNULL(node)) return;
    _destroynode(node);
}

static inline void autonodeattr(Leader *leader, noder node)
{
    if(ISNULL(node->spot->parent))
    {
        setnodeisroot(node);
        setrootnode(leader, node);
    }else if(hasChildren(node)){
        setnodeistrunk(node);
    }else{
        setnodeisleaf(node);
    }
}

void settreenodeleft(Leader *leader, noder node, noder left)
/*向node加入左子节点*/
{
    if(node == NULL) return;
    node->spot->left = left;
    left->spot->parent = node;
    autonodeattr(leader,node);
}

void settreenoderight(Leader *leader,noder node, noder right)
/*向node加入右子节点*/
{
    if(node == NULL) return;
    node->spot->right = right;
    right->spot->parent = node;
    autonodeattr(leader,node);
}
static inline void _rotatenodeleft_root(Leader *leader, noder root)
{
    noder right = root->spot->right;
    if(ISNOTNULL(right)){
        right->spot->parent = NULL;
        root->spot->parent = right;
        if(ISNOTNULL(right->spot->left))
        {
            EXCHAN_GTARGET_NODE(root, right, right, left);
        } else {
            root->spot->right = NULL;
        }
        right->spot->left = root;
        autonodeattr(leader, right);
        autonodeattr(leader, root);
    }
}
static inline void _rotatenodeleft_trunk(Leader *leader, noder trunk)
{
    noder parent = trunk->spot->parent;
    if(ISNOTNULL(trunk->spot->right))
    {
        if(ISNOTNULL(parent->spot->left) && isequare(parent->spot->left->key, trunk->key))
        {
            EXCHAN_GTARGET_NODE(parent, trunk, left, right);
            if(ISNOTNULL(parent->spot->left->spot->left))
            {
                trunk->spot->right = parent->spot->left->spot->left;
                trunk->spot->right->spot->parent = trunk;
            } else {
                trunk->spot->right = NULL;
            }
            trunk->spot->parent = parent->spot->left;
            parent->spot->left->spot->left = trunk;
            autonodeattr(leader, parent->spot->left);
        } else if(ISNOTNULL(parent->spot->right) && isequare(parent->spot->right->key, trunk->key)) {
            EXCHAN_GTARGET_NODE(parent, trunk, right, right);
            if(ISNOTNULL(parent->spot->right->spot->left))
            {
                trunk->spot->right = parent->spot->right->spot->left;
                trunk->spot->right->spot->parent = trunk;

            } else {
                trunk->spot->right = NULL;
            }
            trunk->spot->parent = parent->spot->right;
            parent->spot->right->spot->left = trunk;
            autonodeattr(leader, parent->spot->right);
        }
    }
}

static inline void _rotatenoderight_root(Leader *leader, noder root)
{
    noder left = root->spot->left;
    if(ISNOTNULL(left)){
        left->spot->parent = NULL;
        root->spot->parent = left;
        if(ISNOTNULL(left->spot->right))
        {
            EXCHAN_GTARGET_NODE(root, left, left, right);
        } else {
            root->spot->left = NULL;
        }
        left->spot->right = root;
        autonodeattr(leader,left);
        autonodeattr(leader, root);
    }
}
static inline void _rotatenoderight_trunk(Leader *leader, noder trunk)
{
    noder parent = trunk->spot->parent;
    if(ISNOTNULL(trunk->spot->left))
    {
        if(ISNOTNULL(parent->spot->left) && isequare(parent->spot->left->key, trunk->key))
        {
            EXCHAN_GTARGET_NODE(parent, trunk, left, left);
            if(ISNOTNULL(parent->spot->left->spot->right))
            {
                trunk->spot->left = parent->spot->left->spot->right;
                trunk->spot->left->spot->parent = trunk;
            } else {
                trunk->spot->left = NULL;
            }
            trunk->spot->parent = parent->spot->left;
            parent->spot->left->spot->right = trunk;
            autonodeattr(leader, parent->spot->left);
        } else if(ISNOTNULL(parent->spot->right) && isequare(parent->spot->right->key, trunk->key)) {
            EXCHAN_GTARGET_NODE(parent, trunk, right, left);
            if(ISNOTNULL(parent->spot->right->spot->right))
            {
                trunk->spot->left = parent->spot->right->spot->right;
                trunk->spot->left->spot->parent = trunk;

            } else {
                trunk->spot->left = NULL;
            }
            trunk->spot->parent = parent->spot->right;
            parent->spot->right->spot->right = trunk;
            autonodeattr(leader, parent->spot->right);
        }
    }
}
/**
 * 前序遍历
 * @param node
 * @param key
 * @param type 0，当找不到数据时返回上一节点， 1。只返回查到的数据否则为NULL
 * @return
 */
static inline noder _selectnodebybefor(noder node, char * key, int type)
/*前序遍历的顺序是根节点、左节点、右节点*/
{
    if(!key) return NULL;
    if(ISNULL(node)) return NULL;
    if(isequare(node->key, key)) return node;   // 已经存在
    if(hashcmp(node->key, key)>0)
    {
        noder left = node->spot->left;
        if(ISNULL(left))
            if(type == 0)
                return node;
            else if(type == 1) return NULL;
        _selectnodebybefor(left, key, type);
    } else {
        noder right = node->spot->right;
        if(ISNULL(right))
            if(type == 0)
                return node;
            else if(type == 1) return NULL;
        _selectnodebybefor(right, key, type);
    }
}
static inline noder _select_by_before(noder node1, noder node2)
{
    return _selectnodebybefor(node1, node2->key, 0);
}
static inline noder _select_by_middle(noder node1, noder node2)
/*中序遍历的顺序是左节点、根节点、右节点*/
{
    if(isequare(node1->key, node2->key)) return node1;   // 已经存在
    //TODO
}
static inline noder _select_by_after(noder node1, noder node2)
/*后序遍历的顺序是左节点、右节点、根节点*/
{
    if(isequare(node1->key, node2->key)) return node1;   // 已经存在
    //TODO
}

static inline void _changenodeattr(Leader *leader, noder desc, noder sre)
/*替换节点属性 sre替换掉desc节点*/
{
    if(!(ISNOTNULL(sre) && ISNOTNULL(sre->key) && ISNOTNULL(desc) && ISNOTNULL(desc->key))) return;
    desc->attr = sre->attr;
    desc->color = sre->color;
    noder parent = sre->spot->parent;
    if(ISNOTNULL(parent) && ISNOTNULL(parent->key))
        if(ISNOTNULL(parent->spot->left)&&isequare(parent->spot->left->key, sre->key))
            parent->spot->left = desc;
        else if(ISNOTNULL(parent->spot->right)&& isequare(parent->spot->right->key, sre->key))
            parent->spot->right = desc;
    if(checknodeattr(sre, NODE_ATTR_ISROOT))
        setrootnode(leader, desc);
    EXCHANG_NODE(desc, sre);
    EXCHANG_PARENT(desc, sre);
}

static inline void _changenodeattranddestroy(Leader *leader, noder desc, noder sre)
{
    _changenodeattr(leader, desc, sre);
    if(ISNOTNULL(sre))
        treenodedestroy(sre);
}
static inline void _exchangenodeval(Leader *leader, noder desc, noder sre)
// 交换desc和sre节点值
{
//    desc->key = strcpyautolen(desc->key, sre->key);
//    desc->spot->value = char*cpy(desc->spot->value, sre->spot->value);
    char * key_t = desc->key;
    desc->key = sre->key;
    sre->key = key_t;
    char* val_t = desc->spot->value;
    desc->spot->value = sre->spot->value;
    sre->spot->value = val_t;
}
static inline noder _getbeforenode(noder node)
/*获取前驱节点*/
{
    if(ISNULL(node) || ISNULL(node->key)) return NULL;
    if(ISNULL(node->spot->right))
        return node;
    else _getbeforenode(node->spot->right);
}
static inline noder _getafternode(noder node)
{
    if(ISNULL(node) || ISNULL(node->key)) return NULL;
    if(ISNULL(node->spot->left))
        return node;
    else _getafternode(node->spot->left);
}
noder gettreebeforenode(noder node)
/*获取前驱节点*/
{
    if(!(ISNOTNULL(node) && ISNOTNULL(node->key) && ISNOTNULL(node->spot->left) && ISNOTNULL(node->spot->left->key))) return NULL;
    return _getbeforenode(node->spot->left);
}
noder gettreeafternode(noder node)
/*获取后继节点*/
{
    if(!(ISNOTNULL(node) && ISNOTNULL(node->key) && ISNOTNULL(node->spot->right) && ISNOTNULL(node->spot->right->key))) return NULL;
    return _getafternode(node->spot->right);
}
static inline BOOL _addnode(Leader *leader, noder node)
/*node待加入的节点*/
{
    noder _node = _select_by_before(leader->root_node, node);
    if(ISNULL(_node) || ISNULL(node) || ISNULL(_node->key) || ISNULL(node->key)) return FALSE;
    if(isequare(_node->key, node->key)) return FALSE;
    if(hashcmp(_node->key, node->key)>0)
    {
        noder left = _node->spot->left;
        if(ISNOTNULL(left))
        {
            left->spot->parent = node;
            node->spot->left = left;
            noder leftright = left->spot->right;
            if(ISNOTNULL(leftright))
            {
                settreenoderight(leader, node, leftright);
                left->spot->right = NULL;
            }
        }
        settreenodeleft(leader, _node, node);
    } else {
        noder right = _node->spot->right;
        if(ISNOTNULL(right))
        {
            right->spot->parent = node;
            node->spot->left = right;
            noder rightleft = right->spot->left;
            if(ISNOTNULL(rightleft))
            {
                settreenodeleft(leader, node, rightleft);
                right->spot->left = NULL;
            }
        }
        settreenoderight(leader, _node, node);
    }

    if(!checknodeattr(_node, NODE_ATTR_ISROOT) && !checknodeattr(_node, NODE_ATTR_ISTRUNCK))
        setnodeistrunk(_node);
    return TRUE;
}

static inline void _rotatenodeleftobj(Leader *leader, noder node)
/*左旋*/
{
    if(ISNULL(node)) return;
    if(ISNOTNULL(node->spot->parent))
    {
        _rotatenodeleft_trunk(leader, node);
    } else {
        _rotatenodeleft_root(leader, node);
    }
    autonodeattr(leader, node);
}
static inline void _rotatenoderightobj(Leader *leader, noder node)
/*右旋*/
{
    if(ISNULL(node)) return;
    if(ISNOTNULL(node->spot->parent))
    {
        _rotatenoderight_trunk(leader, node);
    } else {
        _rotatenoderight_root(leader, node);
    }
    autonodeattr(leader, node);
}
static inline int _delnode(Leader *leader, noder node)
{
    if(ISNULL(node)|| ISNULL(node->key)) return 0;
    if(checknodeattr(node, NODE_ATTR_ISROOT)
       && ISNULL(node->spot->left)
       && ISNULL(node->spot->right))
        /*只剩根节点时单独处理*/
    {
        treenodedestroy(node);
        setrootnode(leader, node = NULL);
        return 1;
    }
    if(checknodeattr(node, NODE_ATTR_ISLEAF))
        /*如果是叶子节点*/
    {
        noder parent = node->spot->parent;
        if(ISNOTNULL(parent)){
            if(ISNOTNULL(parent->spot->left) && isequare(parent->spot->left->key, node->key))
            {
                parent->spot->left = NULL;
            } else if(ISNOTNULL(parent->spot->right) && isequare(parent->spot->right->key, node->key)) {
                parent->spot->right = NULL;
            }
            treenodedestroy(node);
            node = NULL;
            //如果不存在左右节点则parent节点成为叶子节点
            if(!checknodeattr(parent, NODE_ATTR_ISROOT) && ISNULL(parent->spot->left) && ISNULL(parent->spot->right))
                setnodeisleaf(parent);
        }
        return 1;
    }
    if(checknodeattr(node, NODE_ATTR_ISTRUNCK) || checknodeattr(node, NODE_ATTR_ISROOT))
    {
        if(ISNOTNULL(node->spot->left) && ISNULL(node->spot->right))
            /*只存在左节点 将删除节点的左子树，挂到父节点上占用被删掉的位置*/
        {
            noder parent = node->spot->parent;
            if(ISNOTNULL(parent)){
                if(ISNOTNULL(parent->spot->left) && isequare(parent->spot->left->key, node->key))
                {
                    EXCHAN_GTARGET_NODE(parent, node, left, left);
                } else if(ISNOTNULL(parent->spot->right) && isequare(parent->spot->right->key, node->key)) {
                    EXCHAN_GTARGET_NODE(parent, node, right, left);
                }
                treenodedestroy(node);
                node = NULL;
            }else{
                // 当前节点为根节点
                leader->root_node = node->spot->left;
                leader->root_node->spot->parent = NULL;
                treenodedestroy(node);
                autonodeattr(leader, leader->root_node);
            }
            return 1;
        }else if(ISNULL(node->spot->left) && ISNOTNULL(node->spot->right))
            /*只存在右节点 将删除节点的右子树，挂到父节点上占用被删掉的位置*/
        {
            noder parent = node->spot->parent;
            if(ISNOTNULL(parent)){
                if(ISNOTNULL(parent->spot->left) && isequare(parent->spot->left->key, node->key))
                {
                    EXCHAN_GTARGET_NODE(parent, node, left, right);
                } else if(ISNOTNULL(parent->spot->right) && isequare(parent->spot->right->key, node->key)) {
                    EXCHAN_GTARGET_NODE(parent, node, right, right);
                }
                treenodedestroy(node);
                node = NULL;
            }else{
                //当前节点为根节点
                leader->root_node = node->spot->right;
                leader->root_node->spot->parent = NULL;
                treenodedestroy(node);
                autonodeattr(leader, leader->root_node);
            }
        }else if(ISNOTNULL(node->spot->left) && ISNOTNULL(node->spot->right))
            /*既存在左节点，又存在右节点 有两种方式*/
            /*  1、将后继节点的值覆盖删除节点的值，并将后继节点的右子树挂到后继节点的父节点上
                2、将前驱节点的值覆盖删除节点的值，并将后继节点的左子树挂到后继节点的父节点上     */
            /*这里使用第一种方法*/
        {
            noder afternode = gettreeafternode(node);
            noder afterleft_childnode = afternode->spot->left;
            noder afterright_childnode = afternode->spot->right;
            noder parent = afternode->spot->parent;
            if(ISNOTNULL(parent) && !hasBrother(afternode) && !hasChildren(afternode))
                //如果后继节点没有兄弟节点或子节点则将父节点置位叶子节点
                setnodeisleaf(parent);
            if(isequare(parent->spot->left->key, afternode->key)){
                parent->spot->left = (ISNOTNULL(afterleft_childnode) && ISNOTNULL(afterleft_childnode->key) && (afterleft_childnode->spot->parent = parent) == parent)?
                                     afterleft_childnode:
                                     (ISNOTNULL(afterright_childnode) && ISNOTNULL(afterright_childnode->key)&&  (afterright_childnode->spot->parent = parent) == parent)?afterright_childnode:NULL;

            }
            else if(isequare(parent->spot->right->key, afternode->key)){
                parent->spot->right = (ISNOTNULL(afterleft_childnode) && ISNOTNULL(afterleft_childnode->key) &&  (afterleft_childnode->spot->parent = parent) == parent)?
                                      afterleft_childnode:
                                      (ISNOTNULL(afterright_childnode) && ISNOTNULL(afterright_childnode->key)&&  (afterright_childnode->spot->parent = parent) == parent)?afterright_childnode:NULL;

            }
            _changenodeattranddestroy(leader, afternode, node);
        }
        return 1;
    }
    return 0;
}

BOOL checknodeattr(noder node, int attr)
{
    switch (attr) {
        case NODE_ATTR_ISROOT:
            return NODEATTR(NODE_ATTR_ISROOT);
        case NODE_ATTR_ISTRUNCK:
            return NODEATTR(NODE_ATTR_ISTRUNCK);
        case NODE_ATTR_ISLEAF:
            return NODEATTR(NODE_ATTR_ISLEAF);
    }
    return FALSE;
}
BOOL hasBrother(noder node)
/*当前节点是否存在兄弟节点*/
{
    if(ISNULL(node) || ISNULL(node->spot->parent)) return FALSE;
    return ISNULL(node->spot->parent->spot->left) || ISNULL(node->spot->parent->spot->right) ? FALSE:TRUE;
}
noder getBrother(noder node)
/*获取点前节点的兄弟节点*/
{
    if(!hasBrother(node)) return NULL;
    if(hasBrother(node))
        if(!isnodeequare(node, node->spot->parent->spot->left))
            return node->spot->parent->spot->left;
    if(!isnodeequare(node, node->spot->parent->spot->right))
        return node->spot->parent->spot->right;
}
BOOL hasChildren(noder node)
/*当前节点是否存在兄弟节点*/
{
    return ISNOTNULL(node->spot->left) || ISNOTNULL(node->spot->right) ? TRUE:FALSE;
}
static inline BOOL _addnodeobj(Leader *leader, noder node)
{
    if(ISNULL(node)) return FALSE;
    if(ISNULL(leader->root_node))
    {
        setrootnode(leader, node);
        setnodeisroot(node);
        return TRUE;
    }else {
        return _addnode(leader, node);
    }
}
void treenodeadd(Leader *leader, char *key, void *value)
{
    noder want_add_node = treenodenew(key, value);
    if(ISNOTNULL(want_add_node))
        _addnodeobj(leader, want_add_node);
}
int treenodedel(Leader *leader, char *key)
/*删除一个节点*/
{
    noder node = treenodesel(leader, key, SELECT_NODE_BEFOR);
    return _delnode(leader,node);
}

noder treenodesel(Leader *leader, char *key, int type)
/*查询节点*/
{

    switch (type) {
        case SELECT_NODE_BEFOR:
            return _selectnodebybefor(leader->root_node, key, 1);
        case SELECT_NODE_MIDDLE:
            return NULL;
        case SELECT_NODE_AFTER:
            return NULL;
    }
}

int treenodemodify(Leader *leader, char *key, void *newvalue)
{
    noder node = treenodesel(leader, key, SELECT_NODE_BEFOR);
    if(ISNULL(node)) return 0;
    noder newnode = _newnode(key, newvalue, 0);
    if(ISNULL(newnode)) return 0;
    _changenodeattranddestroy(leader, newnode, node);
    return 1;
}

void treerotatenodeleft(Leader *leader, char *key)
{
    noder want_rot_node = treenodesel(leader, key, SELECT_NODE_BEFOR);
    if(ISNOTNULL(want_rot_node))
        _rotatenodeleftobj(leader, want_rot_node);
}
void treerotatenoderight(Leader *leader, char *key)
{
    noder want_rot_node = treenodesel(leader, key, SELECT_NODE_BEFOR);
    if(ISNOTNULL(want_rot_node))
        _rotatenoderightobj(leader, want_rot_node);
}
static inline int* _treenodenum(noder node, int *num)
{
    if(ISNULL(node->spot->left) && ISNULL(node->spot->right)) return num;
    if(ISNOTNULL(node->spot->left))
    {
        (*num)++;
        _treenodenum(node->spot->left, num);
    }
    if(ISNOTNULL(node->spot->right))
    {
        (*num)++;
        _treenodenum(node->spot->right, num);
    }

    return num;
}

int treenodenum(noder node)
/*获取树节点树*/
{
    if(ISNULL(node) || ISNULL(node->key)) return 0;
    int num = 1;
    _treenodenum(node, &num);
}
static inline int* _treenodemaxdeep(noder node, int *deep, int *maxdeep)
{
    if(ISNULL(node->spot->left) && ISNULL(node->spot->right))
    {
        (*maxdeep) = (*deep) > (*maxdeep)?(*deep):(*maxdeep);
    }
    if(ISNOTNULL(node->spot->left))
    {
        (*deep)++;
        _treenodemaxdeep(node->spot->left, deep, maxdeep);
        (*deep)--;
    }
    if(ISNOTNULL(node->spot->right))
    {
        (*deep)++;
        _treenodemaxdeep(node->spot->right, deep, maxdeep);
        (*deep)--;
    }
    return deep;
}

int treenodemaxdeep(noder node)
/*获取树的最大深度*/
{
    if(ISNULL(node) || ISNULL(node->key)) return 0;
    int maxdeep = 1;
    int deep = 1;
    _treenodemaxdeep(node, &deep, &maxdeep);
    return maxdeep;
}
/* ================ end of tree.c ================ */

/* ================ start of AVL tree.c ================ */
static inline uint8_t _balanceval(noder node)
/*判断节点是否平衡左右子树差不大于1*/
{
    if(ISNULL(node)) return 0;
    int leftdeep = treenodemaxdeep(node->spot->left);
    int rightdeep = treenodemaxdeep(node->spot->right);
    return (abs(leftdeep-rightdeep) > 1)? (leftdeep > rightdeep?NO_BALANCE_LEFT:NO_BALANCE_RIGHT): 0b00000000;
}
static inline uint8_t _NVLnodeisnobalancedir(noder node, noder *cur)
/*判断失衡方向*/
{
    if(ISNULL(node) && (!_balanceval(node))) return 0;
    uint8_t rest = 0b00000000;
    switch (_balanceval(node)) {
        case NO_BALANCE_LEFT:
        {
            *cur = node->spot->left;
            rest |= NO_BALANCE_P_LEFT;
            if(ISNOTNULL((*cur)->spot->left) && ISNULL((*cur)->spot->right))
            {
                rest |= NO_BALANCE_C_LEFT;
            }else if(ISNOTNULL((*cur)->spot->right) && ISNULL((*cur)->spot->left))
            {
                rest |= NO_BALANCE_C_RIGHT;
            }else{
                rest |= treenodemaxdeep((*cur)->spot->left) > treenodemaxdeep((*cur)->spot->right)?NO_BALANCE_C_LEFT:NO_BALANCE_C_RIGHT;
            }
            break;
        }
        case NO_BALANCE_RIGHT:
        {
            *cur = node->spot->right;
            rest |= NO_BALANCE_P_RIGHT;
            if(ISNOTNULL((*cur)->spot->right)&& ISNULL((*cur)->spot->left))
            {
                rest |= NO_BALANCE_C_RIGHT;
            }else if(ISNOTNULL((*cur)->spot->left)&& ISNULL((*cur)->spot->right))
            {
                rest |= NO_BALANCE_C_LEFT;
            }else{
                rest |= treenodemaxdeep((*cur)->spot->left) > treenodemaxdeep((*cur)->spot->right)?NO_BALANCE_C_LEFT:NO_BALANCE_C_RIGHT;
            }
            break;
        }
    }
    return rest;
}
void NVLautobalance(Leader *leader, noder parent)
/*自动平衡*/
{
    noder cur;
    switch (_balanceval(parent)) {
        case NO_BALANCE_LEFT:
        {
            if(_balanceval(parent->spot->left))
                NVLautobalance(leader, parent->spot->left);
            uint8_t nob = _NVLnodeisnobalancedir(parent, &cur);
            if(NO_BALANCE_P_LEFT & NO_BALANCE_MASK & nob)
                /*右右失衡*/
            {
                if(NO_BALANCE_C_RIGHT & NO_BALANCE_MASK & nob)
                    /*右左失衡*/
                {
                    _rotatenodeleftobj(leader, cur);
                    _rotatenoderightobj(leader, parent);
                }else if(NO_BALANCE_C_LEFT & NO_BALANCE_MASK & nob)
                    _rotatenoderightobj(leader, parent);
            }

        }
        case NO_BALANCE_RIGHT:
        {
            if(_balanceval(parent->spot->right))
                NVLautobalance(leader, parent->spot->right);
            uint8_t nob = _NVLnodeisnobalancedir(parent, &cur);
            if(NO_BALANCE_P_RIGHT & NO_BALANCE_MASK & nob)
                /*右右失衡*/
            {
                if(NO_BALANCE_C_LEFT & NO_BALANCE_MASK & nob)
                    /*右左失衡*/
                {
                    _rotatenoderightobj(leader, cur);
                    _rotatenodeleftobj(leader, parent);
                }else if(NO_BALANCE_C_RIGHT & NO_BALANCE_MASK & nob)
                    _rotatenodeleftobj(leader, parent);
            }

        }
    }
}
static inline void _NVLtreenodeaddautobalance(Leader *leader, noder node, noder parent)
{
    noder pa = node->spot->parent;
    noder papa = ISNOTNULL(parent)?parent->spot->parent:NULL;  // 防止旋转后父节点变动
    if(ISNOTNULL(pa))
    {
        NVLautobalance(leader, pa);
        if(ISNOTNULL(papa))
            _NVLtreenodeaddautobalance(leader, pa, papa);
    }
}
void NVLtreenodeadd(Leader *leader, char *key, void *value)
/*添加节点*/
{
    noder want_add_node = treenodenew(key, value);
    if(ISNOTNULL(want_add_node))
        _addnodeobj(leader, want_add_node);
    _NVLtreenodeaddautobalance(leader, want_add_node, want_add_node->spot->parent);
}
void NVLtreenodedel(Leader *leader, char *key)
/*删除节点*/
{
    noder node = treenodesel(leader, key, SELECT_NODE_BEFOR);
    if(ISNULL(node) && ISNULL(node->key)) return;
    noder parent = node->spot->parent;
    if(checknodeattr(node, NODE_ATTR_ISLEAF) ||checknodeattr(node, NODE_ATTR_ISTRUNCK))
        /*删除叶子节点*//*删除枝干节点*/
    {
        _delnode(leader, node);
        NVLautobalance(leader, parent);
    }
    if(checknodeattr(node, NODE_ATTR_ISROOT))
        /*因为我们使用后继节点所以这里只需处理right节点*/
    {
        _delnode(leader, node);
        NVLautobalance(leader, leader->root_node->spot->right);
    }

}
/* ================ end of AVL tree.c ================ */


/* ================ start of rb tree.c ================ */

/**
 *  1、每个节点不是红色就是黑色
    2、根结点是黑色的
    3、如果一个节点是红色的，则它的两个孩子节点是黑色的
    4、对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点
    5、每个叶子节点都是黑色的（空节点也可）
 */
static inline noder _rbtreeunclenode(noder node)
/*获取叔叔节点*/
{
    if(ISNULL(node)
       || ISNULL(node->spot->parent)
       || ISNULL(node->spot->parent->spot->parent)
       || ISNULL(node->spot->parent->spot->parent->spot->left))
        return NULL;
    if(isnodeequare(node->spot->parent, node->spot->parent->spot->parent->spot->left))
    {
        if(ISNULL(node->spot->parent) || ISNULL(node->spot->parent->spot->parent) || ISNULL(node->spot->parent->spot->parent->spot->right))
            return NULL;
        return node->spot->parent->spot->parent->spot->right;
    }
    return node->spot->parent->spot->parent->spot->left;
}

static inline void _rbtreeppapaunode(noder node, noder *g, noder *p, noder *u)
/*获取节点的祖父 父亲 叔叔节点*/
{
    *p = NULL, *g=NULL, *u=NULL;
    if(ISNULL(node)) return;
    *p = node->spot->parent;
    if(ISNULL(node->spot->parent))return;
    *g =  ISNOTNULL(node->spot->parent->spot->parent)?
          node->spot->parent->spot->parent:NULL;
    *u = _rbtreeunclenode(node);
}

static inline uint16_t _rbtreeckeckinsertaspect(Leader *leader, noder node )
/*判断插入的新节点符合哪种情况*/
{
    if(checknodeattr(node, NODE_ATTR_ISROOT))
        /*插入的节点是红黑树的根节点*/
    {
        return RBTREE_INSERT_ASPECT_ONE;
    }
    noder g,p,u;
    _rbtreeppapaunode(node, &g, &p, &u);
    if(!(p->color^RBTREE_COLOR_BLACK))
        /*父节点是黑色的情况*/
    {
        return RBTREE_INSERT_ASPECT_TWO;
    }
    if(!(p->color^RBTREE_COLOR_RED) && (ISNOTNULL(u)&&!(u->color^RBTREE_COLOR_RED)))
        /*父节点和叔叔节点都是红色*/
    {
        return RBTREE_INSERT_ASPECT_THREE;
    }
    if(!(p->color^RBTREE_COLOR_RED)
       && (ISNULL(u)||!(u->color^RBTREE_COLOR_BLACK))
       && (ISNOTNULL(p->spot->right)&&isnodeequare(node, p->spot->right)))
        /*N 的父节点为红色，叔叔节点没有或为黑色。节点 N 是 P 的右孩子*/
    {
        if(ISNOTNULL(g) && ISNOTNULL(g->spot->left) && isnodeequare(p, g->spot->left))//且节点 P 是 G 的左孩子
            return RBTREE_INSERT_ASPECT_FORE_C_ONE;
        else if(ISNOTNULL(g) && ISNOTNULL(g->spot->right)&&isnodeequare(p, g->spot->right)) //且节点 P 是 G 的右孩子
            return RBTREE_INSERT_ASPECT_FIVE_C_TWO;
    }
    if(!(p->color^RBTREE_COLOR_RED)
       && (ISNULL(u)||!(u->color^RBTREE_COLOR_BLACK))
       && (ISNOTNULL(p->spot->left)&&isnodeequare(node, p->spot->left)))
        /*N 的父节点为红色，叔叔节点没有或为黑色。N 是 P 的左孩子。*/
    {
        if(ISNOTNULL(g) && ISNOTNULL(g->spot->left)&&isnodeequare(p, g->spot->left)) //且节点 P 是 G 的左孩子
            return RBTREE_INSERT_ASPECT_FIVE_C_ONE;

        else if(ISNOTNULL(g) && ISNOTNULL(g->spot->right)&&isnodeequare(p, g->spot->right)) //且节点 P 是 G 的右孩子
            return RBTREE_INSERT_ASPECT_FORE_C_TWO;
    }
}

static inline void _rbtreeinsertautobalance(Leader *leader, noder node)
/*红黑树插入自动平衡模块*/
{
    noder g,p,u;
    _rbtreeppapaunode(node, &g, &p, &u);
    switch (_rbtreeckeckinsertaspect(leader, node)) {
        case RBTREE_INSERT_ASPECT_ONE:
//            直接让新结点变色为黑色
        {
            node->color = RBTREE_COLOR_BLACK;
            break;
        }
        case RBTREE_INSERT_ASPECT_TWO:
//            不需要做任何调整
        {
            break;
        }
        case RBTREE_INSERT_ASPECT_THREE:
//            由于 P 和 N 均为红色，所有性质4被打破，此时需要进行调整。这种情况下，先将 P 和 U 的颜色染成黑色，再将 G 的颜色染成红色。
//            此时经过 G 的路径上的黑色节点数量不变，性质5仍然满足。但需要注意的是 G 被染成红色后，可能会和它的父节点形成连续的红色节点，
//            此时需要递归向上调整。此时需要递归向上调整
        {
            if(ISNOTNULL(p))p->color = RBTREE_COLOR_BLACK;
            if(ISNOTNULL(g))g->color = RBTREE_COLOR_RED;
            if(ISNOTNULL(u))u->color = RBTREE_COLOR_BLACK;
            _rbtreeinsertautobalance(leader, g);
            break;
        }
        case RBTREE_INSERT_ASPECT_FORE_C_ONE:
//            p为g的左孩子 n为p的右孩子 此时先对节点 P 进行左旋，调整 N 与 P 的位置。接下来按照情况五进行处理
        {
            _rotatenodeleftobj(leader, p);
            /*旋转后父子颠倒*/
            noder node_p_t = p;
            p = node;
            node = node_p_t;
        }
        case RBTREE_INSERT_ASPECT_FIVE_C_ONE:
//          p为g的左孩子 n为p的左孩子  此时对 G 进行右旋，调整 P 和 G 的位置，并互换颜色
        {
            _rotatenoderightobj(leader, g);
            uint8_t color_t_g = g->color;
            g->color = p->color;
            p->color = color_t_g;
            break;
        }
        case RBTREE_INSERT_ASPECT_FORE_C_TWO:
//           p为g的右孩子 n为p的左孩子 此时先对节点 P 进行右旋，调整 N 与 P 的位置。接下来按照情况五进行处理
        {
            _rotatenoderightobj(leader, p);
            /*旋转后父子颠倒*/
            noder node_p_t = p;
            p = node;
            node = node_p_t;
        }
        case RBTREE_INSERT_ASPECT_FIVE_C_TWO:
//           p为g的右孩子 n为p的右孩子    此时对 G 进行左旋，调整 P 和 G 的位置，并互换颜色
        {
            _rotatenodeleftobj(leader, g);
            uint8_t color_t_g = g->color;
            g->color = p->color;
            p->color = color_t_g;
            break;
        }
    }

}

int RBtreenodeadd(Leader *leader, char *key, void *value)
/*红黑树插入*/
{
    noder want_add_node = treenodenew(key, value);
    if(ISNOTNULL(want_add_node))
        if(_addnodeobj(leader, want_add_node))
            _rbtreeinsertautobalance(leader, want_add_node);
        else return FALSE;
    return TRUE;
}


/*
 * 二叉树的删除
 */
static inline uint16_t _rbtreeckeckdelaspect(Leader *leader, noder node)
/*红黑树节点删除情况梳理*/
{
    NODE_RELATION_NET(node);
    if(ISNOTNULL(dl) && ISNOTNULL(dr))
//        删除的节点的左、右子树都非空
    {
        return RBTREE_DEL_ASPECT_ONE;
    }

    if(ISNULL(dl) && ISNOTNULL(dr))
//        删除的节点的左子树为空树，右子树非空
    {
        return RBTREE_DEL_ASPECT_TWO;
    }

    if(ISNOTNULL(dl) && ISNULL(dr))
//        删除的节点的右子树为空树，左子树非空
    {
        return RBTREE_DEL_ASPECT_THREE;
    }

    if(ISNULL(dl) && ISNULL(dr))
//        删除的节点的左、右子树都为空树
    {
        return RBTREE_DEL_ASPECT_FORE;
    }
}

/**
 * 当前节点为黑色节点并且这个节点将在树中消失或变为红色时 与之对应的关系网的变化情况
 * @param leader
 * @param node
 */
static inline void _rbtreedelautobalanceincolorline(Leader *leader, noder node)
/*红黑树颜色平衡*/
{
    NODE_RELATION_NET(node);

    if((ISNOTNULL(p)&&!(p->color^RBTREE_COLOR_BLACK))
       && (ISNOTNULL(b)&&!(b->color^RBTREE_COLOR_BLACK))
       && (ISNULL(bl) ||(ISNOTNULL(bl)&&!(bl->color^RBTREE_COLOR_BLACK)))
       && (ISNULL(br) ||(ISNOTNULL(br)&&!(br->color^RBTREE_COLOR_BLACK))))
// 待删除结点的父亲、兄弟、侄子结点为空或是黑色
// 直接把兄弟节点改成红色，这样一来，原本待删除节点后所在的路径少了一个黑色结点，现在兄弟节点所在的路径也少了一个黑色结点，两边“扯平”了。
// 可是，父节点以下的每一条路径都减少了一个黑色结点，与父节点之外的其他路径又造成了新的不平衡啊？
// 没关系，我们让父节点扮演待删除节点的角色，进行递归操作，重新判断各种情况。
    {
        b->color = RBTREE_COLOR_RED;
        _rbtreedelautobalanceincolorline(leader, p);
        return;
    }
    if((ISNOTNULL(p)&& (ISNOTNULL(p)&&!(p->color^RBTREE_COLOR_RED)))
       && (ISNOTNULL(b)&&!(b->color^RBTREE_COLOR_BLACK))
       && (ISNULL(bl) ||(ISNOTNULL(bl)&&!(bl->color^RBTREE_COLOR_BLACK)))
       && (ISNULL(br) ||(ISNOTNULL(br)&&!(br->color^RBTREE_COLOR_BLACK))))
// 待删除结点的父结点是红色，兄弟为黑色，侄子结点为空或是黑色
// 直接让父结点变成黑色，兄弟结点变成红色：
    {
        p->color = RBTREE_COLOR_BLACK;
        b->color = RBTREE_COLOR_RED;
        return;
    }
    if(ISNOTNULL(p)&& (ISNOTNULL(b)&&!(b->color^RBTREE_COLOR_RED)))
// 待删除结点的兄弟结点是红色
// 首先修改父节点的颜色为红色 兄弟节点的颜色为黑色
// 然后以父节点为旋转轴进行旋转（当前节点为父节点的哪个节点就像那个方向旋转）
// 此时待删除节点所在的路径仍然少一个黑色结点 这样的变化会成为 下面情况的某一种 推迟解决
    {

        p->color = RBTREE_COLOR_RED;
        b->color = RBTREE_COLOR_BLACK;
        if(isnodeequare(node, p->spot->left)) _rotatenodeleftobj(leader, p);
        if(isnodeequare(node, p->spot->right)) _rotatenoderightobj(leader, p);
        _rbtreedelautobalanceincolorline(leader, node);
        return;
    }


    if((ISNOTNULL(b)&&!(b->color^RBTREE_COLOR_BLACK) && isnodeequare(b, p->spot->left))
       && (ISNOTNULL(bl)&&!(bl->color^RBTREE_COLOR_RED)))
// 父结点随意，兄弟结点是黑色左孩子，左侄子结点是红色
// 首先将父节点的颜色覆盖兄弟节点的颜色
// 接下来将父节点变为黑色来顶替将要删除的节点, 将左侄子节点的颜色变为黑色来顶替兄弟节点的位置
// 最后以父节点为中心右旋
    {
        b->color = p->color;
        p->color = RBTREE_COLOR_BLACK;
        bl->color = RBTREE_COLOR_BLACK;
        _rotatenoderightobj(leader, p);
        return;
    }

    if((ISNOTNULL(b)&&!(b->color^RBTREE_COLOR_BLACK) && isnodeequare(b, p->spot->left))
       && (ISNOTNULL(br)&&!(br->color^RBTREE_COLOR_RED)))
// 父结点随意，兄弟结点是黑色左孩子，右侄子结点是红色   // TODO
// 首先以兄弟节点为中心左旋
// 接下来右侄子替换成父节点的颜色用来顶替父节点，父节点替换成黑色用来顶替将来被删掉的节点
// 最后以父节点为中心右旋
    {
        if(ISNULL(bl))
            // 左侄子为空 添加一步处理
            // 兄弟节点变父节点的颜色 父节点变黑色 最后以父节点为中心右旋
        {
            b->color = p->color;
            p->color = RBTREE_COLOR_BLACK;
            _rotatenoderightobj(leader, p);
        }else{
            _rotatenodeleftobj(leader, b);
            br->color = p->color;
            p->color = RBTREE_COLOR_BLACK;
            _rotatenoderightobj(leader, p);
        }
        return;
    }
    if((ISNOTNULL(b)&&!(b->color^RBTREE_COLOR_BLACK) && isnodeequare(b, p->spot->right))
       && (ISNOTNULL(br)&&!(br->color^RBTREE_COLOR_RED)))
// 父结点随意，兄弟结点是黑色右孩子，右侄子结点是红色
// 首先将父节点的颜色覆盖兄弟节点的颜色
// 接下来将父节点变为黑色来顶替将要删除的节点, 将右侄子节点的颜色变为黑色来顶替兄弟节点的位置
// 最后以父节点为中心左旋
    {
        b->color = p->color;
        p->color = RBTREE_COLOR_BLACK;
        br->color = RBTREE_COLOR_BLACK;
        _rotatenodeleftobj(leader, p);
        return;
    }

    if((ISNOTNULL(b)&&!(b->color^RBTREE_COLOR_BLACK) && isnodeequare(b, p->spot->right))
       && (ISNOTNULL(bl)&&!(bl->color^RBTREE_COLOR_RED)))
// 父结点随意，兄弟结点是黑色右孩子，左侄子结点是红色
// 首先以兄弟节点为中心右旋
// 接下来左侄子替换成父节点的颜色用来顶替父节点，父节点替换成黑色用来顶替将来被删掉的节点
// 最后以父节点为中心左旋
    {
        if(ISNULL(br))
            // 右侄子为空 添加一步处理
            // 兄弟节点变父节点的颜色 父节点变黑色 最后以父节点为中心左旋
        {
            b->color = p->color;
            p->color = RBTREE_COLOR_BLACK;
            _rotatenodeleftobj(leader, p);
        }else{
            _rotatenoderightobj(leader, b);
            bl->color = p->color;
            p->color = RBTREE_COLOR_BLACK;
            _rotatenodeleftobj(leader, p);
        }
        return;
    }

    /*特殊处理 end*/
    if(ISNOTNULL(p))
        if(!(p->color^RBTREE_COLOR_RED) && ISNULL(b))
        {
            p->color = RBTREE_COLOR_BLACK;
            return;
        }
        else _rbtreedelautobalanceincolorline(leader, p);
    return;
}

static inline void _rbtreedelautobalance(Leader *leader, noder pnode, int *needdel)
/*红黑树删除自动平衡模块*/
{

    NODE_RELATION_NET(pnode);
    switch (_rbtreeckeckdelaspect(leader, pnode)) {
        case RBTREE_DEL_ASPECT_ONE:
            /* 删除节点的左右都不为空的情况
             * 1、 找到待删除节点的后继节点
             * 2、交换待删除节点和后继节点的值，由于后继节点一定是没有左子树，所以转换为 后面三种情况中的 two 和 fore
             * 3、将待删除节点node指向后继节点 改为删除后继节点
             * 4、再次递归调用删除函数
             */
        {
            noder afternode = gettreeafternode(pnode);
            _exchangenodeval(leader, pnode, afternode);
            pnode = afternode;
            _rbtreedelautobalance(leader, node, needdel);
            break;
        }
        case RBTREE_DEL_ASPECT_TWO:
            /* 删除的节点的左子树为空树，右子树非空
             * 1、如果自身是红色由于左子树为空右子树的黑高不计入该节点，整个树形结构的黑高也不计入该节点所以可以按照二叉树的形式直接删除
             * 2、如果自身是黑色右子节点是红色此时，这条路径凭空减少了一个黑色结点，那么我们把右子节点变成黑色即可然后按照二叉树的形式直接删除
             * 3、如果自身是黑色右子节点是黑色或空叶子节点时，此时由于该分支上将少一个黑色节点，需要先处理周围的颜色然后再删除节点。
             */
        {
            if(!(pnode->color^RBTREE_COLOR_RED))
                break;
            if(!(pnode->color^RBTREE_COLOR_BLACK))
                if(ISNOTNULL(dr) && !(dr->color^RBTREE_COLOR_RED) && (dr->color = RBTREE_COLOR_BLACK) == RBTREE_COLOR_BLACK)
                    break;
            if((ISNOTNULL(dr) && !(dr->color^RBTREE_COLOR_BLACK)) || ISNULL(dr))  _rbtreedelautobalanceincolorline(leader, pnode);
            break;
        }
        case RBTREE_DEL_ASPECT_THREE:
            /* 删除的节点的右子树为空树，左子树非空
             * 1、如果自身是红色由于右子树为空左子树的黑高不计入该节点，整个树形结构的黑高也不计入该节点所以可以按照二叉树的形势直接删除
             * 2、如果自身是黑色左子节点是红色此时，这条路径凭空减少了一个黑色结点，那么我们把左子节点变成黑色即可然后按照二叉树的形式直接删除
             * 3、如果自身是黑色左子节点是黑色或空叶子节点时，此时由于该分支上将少一个黑色节点，需要现处理周围的颜色然后再删除节点。
             */

        {
            if(!(pnode->color^RBTREE_COLOR_RED))
                break;
            if(!(pnode->color^RBTREE_COLOR_BLACK))
                if(ISNOTNULL(dl) && !(dl->color^RBTREE_COLOR_RED) && (dl->color = RBTREE_COLOR_BLACK) == RBTREE_COLOR_BLACK)
                    break;
            if((ISNOTNULL(dl) && !(dl->color^RBTREE_COLOR_BLACK)) || ISNULL(dl))  _rbtreedelautobalanceincolorline(leader, pnode);
            break;
        }
        case RBTREE_DEL_ASPECT_FORE:
            /*
             * 删除节点的左右子树都为空的情况
             * :删除节点为红
             * 如果待删除节点为红色那么不用做任何处理直接删除
             * 如果删除节点为黑色那么情况将变复杂以下情况分析为黑节点的情况
             * :删除节点为黑
             * 1、节点为根节点直接删除
             * 2、如果自身是黑色，此时由于删除该节点后该分支上将少一个黑色节点，需要现处理周围的颜色然后再删除节点。
             */
        {
            if(!(pnode->color^RBTREE_COLOR_RED))    // 删除节点为红
                break;
            if(!(pnode->color^RBTREE_COLOR_BLACK))  // 删除节点为黑
            {
                if(checknodeattr(pnode, NODE_ATTR_ISROOT))  // 节点为根节点直接删除
                    break;
                if((ISNOTNULL(pnode->spot->parent->spot->left) && !isnodeequare(pnode, pnode->spot->parent->spot->left))
                   || (ISNOTNULL(pnode->spot->parent->spot->right) && !isnodeequare(pnode, pnode->spot->parent->spot->right))) //节点的父节点还有其他子节点 直接删除（因为此路就不存在了）
                    break;
                else _rbtreedelautobalanceincolorline(leader, pnode);
            }
            break;
        }
    }
}
int RBtreenodedel(Leader *leader, char *key)
/*红黑树删除*/
{
    noder node = treenodesel(leader, key, SELECT_NODE_BEFOR);
    if(ISNULL(node) || ISNULL(node->key)) return FALSE;
    int needdel = 1;
    _rbtreedelautobalance(leader, &node, &needdel);
    if(needdel)
        return _delnode(leader, node);
    return FALSE;
}
noder RBtreenodesel(Leader *leader, char *key)
{
    if(ISNULL(leader)) return NULL;
    return treenodesel(leader, key, SELECT_NODE_BEFOR);
}
/* ================ end of rb tree.c ================ */
